package lcr;

public class Test0076 {
    public static void main(String[] args) {
        int[] dp = {3, 2, 3, 1, 2, 4, 5, 5, 6};
        new Solution0076_1().findKthLargest(dp,4);
    }
}

class Solution0076_1 {
    int[] heap;
    int tailIndex=-1;
    public int findKthLargest(int[] nums, int k) {
        heap=new int[k];
        for (int num : nums)
            if (tailIndex<k-1||num>heap[0])
                add(num);

        return heap[0];
    }

    public void add(int num){
        if (tailIndex<heap.length-1){
            heap[++tailIndex]=num;
            heapifyUp(tailIndex);
        }else {
            swap(heap,tailIndex--,0);
            heapifyDown(0);

            heap[++tailIndex]=num;
            heapifyUp(tailIndex);
        }
    }

    public void heapifyUp(int i){
        if (i<=0) return;
        int num = heap[i];
        int preIndex = preIndex(i);
        if (num<heap[preIndex]){
            swap(heap,preIndex,i);
            heapifyUp(preIndex);
        }
    }

    public void heapifyDown(int i){
        int smallerIndex=i;
        if (i*2+1<=tailIndex&&heap[i*2+1]<heap[smallerIndex]) smallerIndex=i*2+1;
        if (i*2+2<=tailIndex&&heap[i*2+2]<heap[smallerIndex]) smallerIndex=i*2+2;

        if (i!=smallerIndex){
            swap(heap,i,smallerIndex);
            heapifyDown(smallerIndex);
        }
    }

    public void swap(int[] arr,int a,int b){
        int temp = arr[a];
        arr[a]=arr[b];
        arr[b]=temp;
    }

    public int preIndex(int i){
        return (i-1)>>1;
    }
}
